package com.ww.springboot.boot.thread.study.base.lock.aqs.source;

import java.lang.reflect.Field;
import java.util.concurrent.TimeUnit;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Date;
import java.util.concurrent.locks.AbstractOwnableSynchronizer;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.LockSupport;

import lombok.Data;
import sun.misc.Unsafe;

/**
 * 条件节点 阻塞队列 源码还未阅读
 *
 * @author Doug Lea
 * @since 1.5
 */
public abstract class MyAbstractQueuedSynchronizer
        extends AbstractOwnableSynchronizer
        implements java.io.Serializable {

    private static final long serialVersionUID = 7373984972572414691L;


    protected MyAbstractQueuedSynchronizer() {
    }


    public static final class Node {
        /**
         * 标识节点是共享节点
         */
        static final Node SHARED = new Node();
        /**
         * 标识节点是独占节点
         */
        static final Node EXCLUSIVE = null;

        /**
         * 节点已经被取消
         */
        static final int CANCELLED = 1;
        /**
         * 指示后续线程需要unpark-阻塞
         */
        static final int SIGNAL = -1;
        /**
         * waitStatus value to indicate thread is waiting on condition
         * 条件队列时使用
         */
        static final int CONDITION = -2;
        /**
         * waitStatus value to indicate the next acquireShared should
         * unconditionally propagate
         * 共享模式下使用
         */
        static final int PROPAGATE = -3;

        /**
         * 节点状态 默认为0
         * 其他节点
         * <p>
         * {@link Node.CANCELLED}
         * {@link Node.SIGNAL}
         * {@link Node.CONDITION}
         * {@link Node.PROPAGATE}
         * <p>
         * 一共五个状态
         * 一个用于条件节点
         * 一个用于共享节点
         * 一个是默认值
         * 一个是取消值
         * 一个是标志下一个节点需要阻塞的值
         */
        volatile int waitStatus;

        /**
         * 前置节点  --双向链表
         */
        volatile Node prev;

        /**
         * 后置节点  --双向链表
         */
        volatile Node next;


        volatile Thread thread;

        /**
         * 如果是独占节点 则此值为空
         * 如果是共享节点 则此值为共享的其他节点
         * 2.作为指针记录条件队列(等待队列)中的下一个等待节点
         */
        Node nextWaiter;

        /**
         * 判断是否共享节点
         *
         * @return
         */
        final boolean isShared() {
            return nextWaiter == SHARED;
        }

        /**
         * 获取前置节点 ??为什么没有前置节点就报空指针异常
         * ww_s 因为头结点为空节点 因此每个节点一定会有一个前置节点
         *
         * @return
         * @throws NullPointerException
         */
        final Node predecessor() throws NullPointerException {
            Node p = prev;
            if (p == null)
                throw new NullPointerException();
            else
                return p;
        }

        Node() {    // Used to establish initial head or SHARED marker
        }

        Node(Thread thread, Node mode) {     // Used by addWaiter
            this.nextWaiter = mode;
            this.thread = thread;
        }

        Node(Thread thread, int waitStatus) { // Used by Condition
            this.waitStatus = waitStatus;
            this.thread = thread;
        }

        public int getWaitStatus() {
            return waitStatus;
        }

        public Node setWaitStatus(int waitStatus) {
            this.waitStatus = waitStatus;
            return this;
        }

        public Node getPrev() {
            return prev;
        }

        public Node setPrev(Node prev) {
            this.prev = prev;
            return this;
        }

        public Node getNext() {
            return next;
        }

        public Node setNext(Node next) {
            this.next = next;
            return this;
        }

        public Thread getThread() {
            return thread;
        }

        public Node setThread(Thread thread) {
            this.thread = thread;
            return this;
        }

        public Node getNextWaiter() {
            return nextWaiter;
        }

        public Node setNextWaiter(Node nextWaiter) {
            this.nextWaiter = nextWaiter;
            return this;
        }
    }

    /**
     * <ul>
     *     <li> 同步队列头结点  头结点中不包含线程 头结点不参与资源抢占
     *     <li> 竞争发生在加锁时
     *     <li>
     *     <li> * ww_m  将head节点设置为空节点的意义 ？一种设计思路 空节点不必参与竞争 作为指针指向下一个需要执行任务的节点即可
     *                  将head节点设置为空节点的意义2 为了让第一个节点与后面的节点执行相同的逻辑--也就是等待前置节点被唤醒
     *          * ww_m  竞争发生在加锁时
     *     <li>为什么头结点需要设置为空节点?如果直接将线程节点设置为头结点会怎么样?这样每个线程就都会去抢占头结点 竞争会变得更加激烈
     *         线程本身就会有竞争 再去竞争头结点 会更加混乱 因此设计成让前置节点去竞争资源 自己躺平 只用关注自己的任务即可 不用与其他线程节点竞争 只用关心前置节点即可
     * <ul/>
     *
     *
     *

     */
    private transient volatile Node head;

    /**
     * 同步队列尾结点
     * ww_m 队列添加节点方式  先将节点前置指针指向尾节点 当当前节点成功替换为尾节点时 将旧的尾节点后置指针指向新的尾节点
     *      队列解锁是从尾部开始遍历的 --线程并发问题导致只能从尾节点开始
     */
    private transient volatile Node tail;

    public Node getHead() {
        return head;
    }

    public Node getTail() {
        return tail;
    }

    public MyAbstractQueuedSynchronizer setTail(Node tail) {
        this.tail = tail;
        return this;
    }

    /**
     * ww_m int值 默认为0 根据state 来判断是否可以获取锁
     */
    private volatile int state;

    public final int getState() {
        return state;
    }


    public final void setState(int newState) {
        state = newState;
    }

    /**
     * 此方法保证线程安全 即自带锁 不支持并发
     *
     * @param expect
     * @param update
     * @return
     */
    protected final boolean compareAndSetState(int expect, int update) {
        // See below for intrinsics setup to support this
        return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
    }

    static final long spinForTimeoutThreshold = 1000L;


    /**
     * ww_s 如果尾节点为空 则创建一个节点作为头结点 并将尾节点指向头结点
     * 如果尾节点不为空 则说明尾节点变化了 获取到尾节点
     * 自旋 将其加入到尾节点 直到成功
     *
     * @param node
     * @return
     */
    private Node enq(final Node node) {
        for (; ; ) {
            Node t = tail;
            if (t == null) { // Must initialize
                if (compareAndSetHead(new Node()))
                    tail = head;
            } else {
                //ww_m 此处的逻辑导致释放锁只能从后往前遍历  因为并发 情况下t节点的next还没设值 导致查找失败
                //能不能 让t.next先赋值呢 不行 因为一旦没有添加成功 说明t不能尾结点 此时设值t的next 会导致其他节点丢失
                node.prev = t;
                if (compareAndSetTail(t, node)) {
                    t.next = node;
                    return t;
                }
            }
        }
    }

    /**
     * 此接口的目的:将此节点加入到同步队列中
     * 至于是头结点还是尾节点 还是其他情况 根据情况做相应的处理
     * 创建一个节点
     * 1.获取尾节点
     * 尾节点不为空 则将尾节点设置为当前节点的前置节点
     * 如果尾节点没有改变则将当前节点设置为尾节点同时将旧的尾节点的后置节点指向尾节点
     * 如果尾节点为空 或者尾节点变化 则继续尝试将节点加入到同步队列
     *
     * @param mode Node.EXCLUSIVE for exclusive, Node.SHARED for shared
     * @return the new node
     */
    private Node addWaiter(Node mode) {
        Node node = new Node(Thread.currentThread(), mode);
        // Try the fast path of enq; backup to full enq on failure
        Node pred = tail;
        if (pred != null) {
            node.prev = pred;
            if (compareAndSetTail(pred, node)) {
                //compareAndSetTail保证此处线程安全
                pred.next = node;
                return node;
            }
        }
        enq(node);
        return node;
    }

    /**
     * 设置节点为head节点 head节点的thread和prev属性无用置为0
     *
     * @param node the node
     */
    private void setHead(Node node) {
        head = node;
        node.thread = null;
        node.prev = null;
    }

    /**
     * <ul>
     * <li> 目的：唤醒符合条件的节点-
     * <li> 逻辑：从尾节点开始遍历 找到最前面的符合条件的一个节点并唤醒
     * <li> 注意事项：一次只唤醒一个节点
     * </ul>
     * <p>
     * node为head节点
     *
     * @param node the node
     */
    private void unparkSuccessor(Node node) {
        /*
         * If status is negative (i.e., possibly needing signal) try
         * to clear in anticipation of signalling.  It is OK if this
         * fails or if status is changed by waiting thread.
         *
         * 暂时不理解此逻辑的含义
         */
        int ws = node.waitStatus;
        if (ws < 0)
            compareAndSetWaitStatus(node, ws, 0);

        /*
         * Thread to unpark is held in successor, which is normally
         * just the next node.  But if cancelled or apparently null,
         * traverse backwards from tail to find the actual
         * non-cancelled successor.
         */
        Node s = node.next;
        if (s == null || s.waitStatus > 0) {
            //如果头结点的后置节点为空或者为canceled 则从后遍历获取最后一个状态为正常的节点？？为什么不从头结点开始找
            s = null;
            for (Node t = tail; t != null && t != node; t = t.prev)
                if (t.waitStatus <= 0)
                    s = t;
        }
        if (s != null)
            //如果节点不为空 则唤醒此节点的线程 此节点会在之前休眠的地方重启并尝试获取锁
            //如果节点为空 则说明没有需要唤醒的线程 所以不用考虑未唤醒节点的场景
            LockSupport.unpark(s.thread);
    }

    /**
     * 1.设置头结点为0或者PROPAGATE 然后唤醒一个节点 如果头结点发生变化 则继续执行1
     * 1.SIGNAL->0  2.0->PROPAGATE 只有1的场景才会唤醒线程 2的场景标识此次不唤醒 等待标识变为SIGNAL再唤醒
     * 此方法是为了将所有的可唤醒线程一起唤醒 然后一起释放
     */
    private void doReleaseShared() {
        for (; ; ) {
            //此head是已经更新过后的head
            Node h = head;
            //如果队列中存在线程
            if (h != null && h != tail) {
                int ws = h.waitStatus;
                //如果头节点状态是正常唤醒状态
                if (ws == Node.SIGNAL) {
                    //循环直到设置为0
                    if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))
                        continue;            // loop to recheck cases
                    //唤醒线程 这个地方其实是一个递归过程 第一个节点负责唤醒下一个可唤醒的节点
                    unparkSuccessor(h);
                } else if (ws == 0 &&
                        !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
                    continue;                // loop on failed CAS
            }
            //如果head 改变了就一直循环 直到head不再改变
            //此处不用担心 判断逻辑与head赋值的先后顺序 如果head变了就等着一起 如果没有变就自己先走 新的head节点依旧可以重复解锁逻辑并返回
            //此处的设计是为了保证如果解锁时发现有并发线程就等待着一起释放
            if (h == head)                   // loop if head changed
                break;
        }
    }

    /**
     * 暂时读不懂为什么这么设计
     * 将当前节点设置为头结点 ？？？头结点什么时候会为空
     * 只要后面还有共享节点或者propagate>0 就继续触发释放锁逻辑 直到没有符合条件的节点
     *
     * @param node      the node
     * @param propagate the return value from a tryAcquireShared
     */
    private void setHeadAndPropagate(Node node, int propagate) {
        //获取头结点
        Node h = head; // Record old head for check below
        //设置头结点
        setHead(node);
        /*
         * Try to signal next queued node if:
         *   Propagation was indicated by caller,
         *     or was recorded (as h.waitStatus either before
         *     or after setHead) by a previous operation
         *     (note: this uses sign-check of waitStatus because
         *      PROPAGATE status may transition to SIGNAL.)
         * and
         *   The next node is waiting in shared mode,
         *     or we don't know, because it appears null
         *
         * The conservatism in both of these checks may cause
         * unnecessary wake-ups, but only when there are multiple
         * racing acquires/releases, so most need signals now or soon
         * anyway.
         */
        //此处判断逻辑不清楚 肯定是为了将所有的可能的情况都包含
        if (propagate > 0 || h == null || h.waitStatus < 0 ||
                (h = head) == null || h.waitStatus < 0) {
            //获取当前节点的后置节点 如果后置节点为空 或者后置及节点为共享锁
            Node s = node.next;
            if (s == null || s.isShared())
                //释放共享锁
                doReleaseShared();
        }
    }

    // Utilities for various versions of acquire

    /**
     * 关闭节点
     *
     * @param node the node
     */
    private void cancelAcquire(Node node) {
        // Ignore if node doesn't exist
        if (node == null)
            return;

        node.thread = null;

        // Skip cancelled predecessors
        Node pred = node.prev;
        while (pred.waitStatus > 0)
            node.prev = pred = pred.prev;

        // predNext is the apparent node to unsplice. CASes below will
        // fail if not, in which case, we lost race vs another cancel
        // or signal, so no further action is necessary.
        Node predNext = pred.next;

        // Can use unconditional write instead of CAS here.
        // After this atomic step, other Nodes can skip past us.
        // Before, we are free of interference from other threads.
        node.waitStatus = Node.CANCELLED;

        // If we are the tail, remove ourselves.
        if (node == tail && compareAndSetTail(node, pred)) {
            compareAndSetNext(pred, predNext, null);
        } else {
            // If successor needs signal, try to set pred's next-link
            // so it will get one. Otherwise wake it up to propagate.
            int ws;
            if (pred != head &&
                    ((ws = pred.waitStatus) == Node.SIGNAL ||
                            (ws <= 0 && compareAndSetWaitStatus(pred, ws, Node.SIGNAL))) &&
                    pred.thread != null) {
                Node next = node.next;
                if (next != null && next.waitStatus <= 0)
                    compareAndSetNext(pred, predNext, next);
            } else {
                unparkSuccessor(node);
            }

            node.next = node; // help GC
        }
    }

    /**
     * 此方法目的：
     * 获取锁失败后park 阻塞线程 避免不必要的自旋
     * 逻辑:
     * 判断前置节点的状态
     * 如果前置节点的状态是SIGNAL 则返回true 及将当前节点阻塞
     * 如果前置节点的状态是CANCELLED 则将此节点前移丢弃前置节点
     * 如果是其他状态则将前置节点设置为SIGNAL ?? 猜测:保证前置节点是SIGNAL状态 当前置节点为SIGNAL是 可以将自己节点对应的线程置于休眠状态 避免自旋消耗性能
     * 前置节点为SIGNAL时 后置节点就可以休眠了 等待在其他地方被唤醒???再哪唤醒的呢? 在解锁的地方唤醒
     *
     * @param pred
     * @param node
     * @return
     */
    private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
        int ws = pred.waitStatus;
        if (ws == Node.SIGNAL)
            /*
             * This node has already set status asking a release
             * to signal it, so it can safely park.
             */
            return true;
        if (ws > 0) {
            /*
             * Predecessor was cancelled. Skip over predecessors and
             * indicate retry.
             */
            do {
                node.prev = pred = pred.prev;
            } while (pred.waitStatus > 0);
            pred.next = node;
        } else {
            /*
             * waitStatus must be 0 or PROPAGATE.  Indicate that we
             * need a signal, but don't park yet.  Caller will need to
             * retry to make sure it cannot acquire before parking.
             * ww_m 每个节点第一次获取锁后就会尝试将前置节点状态设置为Node.SIGNAL 如果设置成功则阻塞 如果设置不成功则继续尝试获取锁 因为前置节点的状态发生了变化
             */
            compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
        }
        return false;
    }

    /**
     * 目的: 中断当前线程
     */
    static void selfInterrupt() {
        Thread.currentThread().interrupt();
    }

    /**
     * 目的:
     * <ol>
     *     <li>阻塞线程
     *     <li>返回线程中断状态
     * <ol/>
     *
     * @return
     */
    private final boolean parkAndCheckInterrupt() {
        LockSupport.park(this);
        return Thread.interrupted();
    }

    /**
     * 将加入的节点 自旋获取锁
     * 逻辑：自旋 等到此节点的前置节点为头节点并且获取到锁之后才返回
     * 如果获取锁过程中出现异常 则取消节点???
     * <p>
     * 优化：判断当前节点的前置节点状态 如果其前置节点非唤醒状态 则此节点也处于阻塞状态 避免自旋消耗性能
     * 线程的唤醒跟waitStatus无关 释放锁后自然会选择相应的节点进行唤醒
     *
     * @param node
     * @param arg
     * @return
     */
    final boolean acquireQueued(final Node node, int arg) {
        boolean failed = true;
        try {
            boolean interrupted = false;
            for (; ; ) {
                final Node p = node.predecessor();
                if (p == head && tryAcquire(arg)) {
                    //设置当前节点为前置节点
                    setHead(node);
                    p.next = null; // help GC
                    failed = false;
                    return interrupted;
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                        parkAndCheckInterrupt())
                    //当前线程如果中断标识为true的话 则等到获取锁后才会被中断
                    interrupted = true;
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }


    /**
     * 逻辑:此方法与acquire()的区别 就是线程唤醒后会立马相应中断 而acquire()会在获取锁资源后才自行中断
     *
     * @param arg
     * @throws InterruptedException
     */
    private void doAcquireInterruptibly(int arg)
            throws InterruptedException {
        final Node node = addWaiter(Node.EXCLUSIVE);
        boolean failed = true;
        try {
            for (; ; ) {
                final Node p = node.predecessor();
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null; // help GC
                    failed = false;
                    return;
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                        parkAndCheckInterrupt())
                    //与 acquire 的区别 线程中断标识为true的话 直接抛中断异常
                    throw new InterruptedException();
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }


    /**
     * 目的：带超时时间的获取锁 超过时间则马上唤醒 如果依旧获取不到锁 则直接返回获取锁失败
     * @param arg
     * @param nanosTimeout
     * @return
     * @throws InterruptedException
     */
    private boolean doAcquireNanos(int arg, long nanosTimeout)
            throws InterruptedException {
        if (nanosTimeout <= 0L)
            return false;
        final long deadline = System.nanoTime() + nanosTimeout;
        final Node node = addWaiter(Node.EXCLUSIVE);
        boolean failed = true;
        try {
            for (; ; ) {
                final Node p = node.predecessor();
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null; // help GC
                    failed = false;
                    return true;
                }
                nanosTimeout = deadline - System.nanoTime();
                if (nanosTimeout <= 0L)
                    return false;
                if (shouldParkAfterFailedAcquire(p, node) &&
                        nanosTimeout > spinForTimeoutThreshold)
                    LockSupport.parkNanos(this, nanosTimeout);
                if (Thread.interrupted())
                    throw new InterruptedException();
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }


    /**
     * <ul>
     *    <li> 目的:共享式获取锁
     *    <li> 逻辑:如果当前节点的前置节点为头结点 则尝试获取锁 获取成功则将当前节点设置为头结点 并触发唤醒所有线程
     *    <p> 与独占锁的区别
     *    <p>   1.设置head节点的逻辑不一样
     *    <p>   2.节点类型不一样 SHARED
     * </ul>
     * @param arg
     */
    private void doAcquireShared(int arg) {
        final Node node = addWaiter(Node.SHARED);
        boolean failed = true;
        try {
            boolean interrupted = false;
            for (; ; ) {
                final Node p = node.predecessor();
                if (p == head) {
                    int r = tryAcquireShared(arg);
                    if (r >= 0) {
                        setHeadAndPropagate(node, r);
                        p.next = null; // help GC
                        if (interrupted)
                            selfInterrupt();
                        failed = false;
                        return;
                    }
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                        parkAndCheckInterrupt())
                    interrupted = true;
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }


    private void doAcquireSharedInterruptibly(int arg)
            throws InterruptedException {
        final Node node = addWaiter(Node.SHARED);
        boolean failed = true;
        try {
            for (; ; ) {
                final Node p = node.predecessor();
                if (p == head) {
                    int r = tryAcquireShared(arg);
                    if (r >= 0) {
                        setHeadAndPropagate(node, r);
                        p.next = null; // help GC
                        failed = false;
                        return;
                    }
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                        parkAndCheckInterrupt())
                    throw new InterruptedException();
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }


    private boolean doAcquireSharedNanos(int arg, long nanosTimeout)
            throws InterruptedException {
        if (nanosTimeout <= 0L)
            return false;
        final long deadline = System.nanoTime() + nanosTimeout;
        final Node node = addWaiter(Node.SHARED);
        boolean failed = true;
        try {
            for (; ; ) {
                final Node p = node.predecessor();
                if (p == head) {
                    int r = tryAcquireShared(arg);
                    if (r >= 0) {
                        setHeadAndPropagate(node, r);
                        p.next = null; // help GC
                        failed = false;
                        return true;
                    }
                }
                nanosTimeout = deadline - System.nanoTime();
                if (nanosTimeout <= 0L)
                    return false;
                if (shouldParkAfterFailedAcquire(p, node) &&
                        nanosTimeout > spinForTimeoutThreshold)
                    LockSupport.parkNanos(this, nanosTimeout);
                if (Thread.interrupted())
                    throw new InterruptedException();
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

    protected boolean tryAcquire(int arg) {
        throw new UnsupportedOperationException();
    }


    protected boolean tryRelease(int arg) {
        throw new UnsupportedOperationException();
    }


    protected int tryAcquireShared(int arg) {
        throw new UnsupportedOperationException();
    }


    protected boolean tryReleaseShared(int arg) {
        throw new UnsupportedOperationException();
    }


    protected boolean isHeldExclusively() {
        throw new UnsupportedOperationException();
    }


    /**
     * <ul>
     *     <li> 目的：获取锁
     *     <li> <p>逻辑：
     *          <p>    尝试获取锁 失败则加入到同步队列-自旋获取锁
     *          <p>    如果获取锁失败就会自行中断 selfInterrupt
     *     <li> 注意事项：不实时响应中断 只有线程获取到锁之后才会响应中断
     * </ul>
     *
     * @param arg
     */
    public final void acquire(int arg) {
        if (!tryAcquire(arg) &&
                acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
            selfInterrupt();
    }


    /**
     * <ul>
     *     <li> 目的：获取锁 并实时相应中断
     *     <li> <p>逻辑：
     *          <p>     如果线程中断标识为true 则直接报中断异常
     *          <p>     尝试获取锁 失败则加入到同步队列-自旋获取锁 同时在自旋过程中会响应中断
     *     <li> 注意事项：
     *     1.实时响应中断
     *     2.自旋过程中等到被唤醒时未获取到锁则立马响应中断 报中断异常
     *     3.是否响应中断:自旋过程中不用等到获取锁才响应中断
     * </ul>
     *
     * @param arg
     */
    public final void acquireInterruptibly(int arg)
            throws InterruptedException {
        if (Thread.interrupted())
            throw new InterruptedException();
        if (!tryAcquire(arg))
            doAcquireInterruptibly(arg);
    }


    /**
     * 获取锁 等待一定时间
     *
     * @param arg
     * @param nanosTimeout
     * @return
     * @throws InterruptedException
     */
    public final boolean tryAcquireNanos(int arg, long nanosTimeout)
            throws InterruptedException {
        if (Thread.interrupted())
            throw new InterruptedException();
        return tryAcquire(arg) ||
                doAcquireNanos(arg, nanosTimeout);
    }

    /**
     * <ul>
     *     <li> 目的: 释放锁
     *     <li> 逻辑：解锁成功 则获取头结点 从同步队列中唤醒最早的阻塞线程
     *     <li> 注意事项
     * </ul>
     * <p>
     * 加锁的时候只是自旋往同步队列中加节点（此时是有竞争的）
     * <p>
     * 释放锁的时候是从头结点开始往后遍历 直到找到一个可以唤醒并获取锁的节点 （ww_s 此时是无竞争的 因为只有获取到锁的节点才能成功释放锁！！！ 此处是关键:不能让未获取到锁的节点成功释放锁）
     *
     * @param arg
     * @return
     */
    public final boolean release(int arg) {
        if (tryRelease(arg)) {
            Node h = head;
            if (h != null && h.waitStatus != 0)
                unparkSuccessor(h);
            return true;
        }
        return false;
    }


    /**
     * 目的：获取共享锁
     * 小于0时 没有获取到锁 则去自旋获取锁
     *
     * @param arg
     */
    public final void acquireShared(int arg) {
        if (tryAcquireShared(arg) < 0)
            doAcquireShared(arg);
    }


    /**
     * 共享式中断锁
     *
     * @param arg
     * @throws InterruptedException
     */
    public final void acquireSharedInterruptibly(int arg)
            throws InterruptedException {
        if (Thread.interrupted())
            throw new InterruptedException();
        if (tryAcquireShared(arg) < 0)
            doAcquireSharedInterruptibly(arg);
    }

    /**
     * 共享式获取锁++超时时间
     *
     * @param arg
     * @param nanosTimeout
     * @return
     * @throws InterruptedException
     */
    public final boolean tryAcquireSharedNanos(int arg, long nanosTimeout)
            throws InterruptedException {
        if (Thread.interrupted())
            throw new InterruptedException();
        return tryAcquireShared(arg) >= 0 ||
                doAcquireSharedNanos(arg, nanosTimeout);
    }

    /**
     * 释放共享锁
     *
     * @param arg
     * @return
     */
    public final boolean releaseShared(int arg) {
        if (tryReleaseShared(arg)) {
            doReleaseShared();
            return true;
        }
        return false;
    }

    // Queue inspection methods

    /**
     * 同步队列中是否有线程等待
     *
     * @return
     */
    public final boolean hasQueuedThreads() {
        return head != tail;
    }

    /**
     * 是否有头结点
     *
     * @return
     */
    public final boolean hasContended() {
        return head != null;
    }

    /**
     * 获取队列中的第一个线程节点
     *
     * @return
     */
    public final Thread getFirstQueuedThread() {
        // handle only fast path, else relay
        return (head == tail) ? null : fullGetFirstQueuedThread();
    }

    /**
     * 获取队列中的第一个线程节点
     *
     * @return
     */
    private Thread fullGetFirstQueuedThread() {
        /*
         * The first node is normally head.next. Try to get its
         * thread field, ensuring consistent reads: If thread
         * field is nulled out or s.prev is no longer head, then
         * some other thread(s) concurrently performed setHead in
         * between some of our reads. We try this twice before
         * resorting to traversal.
         */
        Node h, s;
        Thread st;
        if (((h = head) != null && (s = h.next) != null &&
                s.prev == head && (st = s.thread) != null) ||
                ((h = head) != null && (s = h.next) != null &&
                        s.prev == head && (st = s.thread) != null))
            return st;

        /*
         * Head's next field might not have been set yet, or may have
         * been unset after setHead. So we must check to see if tail
         * is actually first node. If not, we continue on, safely
         * traversing from tail back to head to find first,
         * guaranteeing termination.
         */

        Node t = tail;
        Thread firstThread = null;
        while (t != null && t != head) {
            Thread tt = t.thread;
            if (tt != null)
                firstThread = tt;
            t = t.prev;
        }
        return firstThread;
    }


    /**
     * 判断当前线程是否在同步队列中
     *
     * @param thread
     * @return
     */
    public final boolean isQueued(Thread thread) {
        if (thread == null)
            throw new NullPointerException();
        for (Node p = tail; p != null; p = p.prev)
            if (p.thread == thread)
                return true;
        return false;
    }

    /**
     * 判断第一个同步队列节点是否独占式的
     *
     * @return
     */
    final boolean apparentlyFirstQueuedIsExclusive() {
        Node h, s;
        return (h = head) != null &&
                (s = h.next) != null &&
                !s.isShared() &&
                s.thread != null;
    }


    /**
     * 是否还有节点等待 ？？？？？
     *
     * @return
     */
    public final boolean hasQueuedPredecessors() {
        // The correctness of this depends on head being initialized
        // before tail and on head.next being accurate if the current
        // thread is first in queue.
        Node t = tail; // Read fields in reverse initialization order
        Node h = head;
        Node s;
        return h != t &&
                ((s = h.next) == null || s.thread != Thread.currentThread());
    }


    // Instrumentation and monitoring methods


    public final int getQueueLength() {
        int n = 0;
        for (Node p = tail; p != null; p = p.prev) {
            if (p.thread != null)
                ++n;
        }
        return n;
    }


    public final Collection<Thread> getQueuedThreads() {
        ArrayList<Thread> list = new ArrayList<Thread>();
        for (Node p = tail; p != null; p = p.prev) {
            Thread t = p.thread;
            if (t != null)
                list.add(t);
        }
        return list;
    }


    /**
     * 获取独占队列线程 从后往前获取
     *
     * @return
     */
    public final Collection<Thread> getExclusiveQueuedThreads() {
        ArrayList<Thread> list = new ArrayList<Thread>();
        for (Node p = tail; p != null; p = p.prev) {
            if (!p.isShared()) {
                Thread t = p.thread;
                if (t != null)
                    list.add(t);
            }
        }
        return list;
    }


    public final Collection<Thread> getSharedQueuedThreads() {
        ArrayList<Thread> list = new ArrayList<Thread>();
        for (Node p = tail; p != null; p = p.prev) {
            if (p.isShared()) {
                Thread t = p.thread;
                if (t != null)
                    list.add(t);
            }
        }
        return list;
    }


    public String toString() {
        int s = getState();
        String q = hasQueuedThreads() ? "non" : "";
        return super.toString() +
                "[State = " + s + ", " + q + "empty queue]";
    }


    // Internal support methods for Conditions


    final boolean isOnSyncQueue(Node node) {
        if (node.waitStatus == Node.CONDITION || node.prev == null)
            return false;
        if (node.next != null) // If has successor, it must be on queue
            return true;
        /*
         * node.prev can be non-null, but not yet on queue because
         * the CAS to place it on queue can fail. So we have to
         * traverse from tail to make sure it actually made it.  It
         * will always be near the tail in calls to this method, and
         * unless the CAS failed (which is unlikely), it will be
         * there, so we hardly ever traverse much.
         */
        return findNodeFromTail(node);
    }


    private boolean findNodeFromTail(Node node) {
        Node t = tail;
        for (; ; ) {
            if (t == node)
                return true;
            if (t == null)
                return false;
            t = t.prev;
        }
    }


    final boolean transferForSignal(Node node) {
        /*
         * If cannot change waitStatus, the node has been cancelled.
         */
        if (!compareAndSetWaitStatus(node, Node.CONDITION, 0))
            return false;

        /*
         * Splice onto queue and try to set waitStatus of predecessor to
         * indicate that thread is (probably) waiting. If cancelled or
         * attempt to set waitStatus fails, wake up to resync (in which
         * case the waitStatus can be transiently and harmlessly wrong).
         */
        Node p = enq(node);
        int ws = p.waitStatus;
        if (ws > 0 || !compareAndSetWaitStatus(p, ws, Node.SIGNAL))
            LockSupport.unpark(node.thread);
        return true;
    }


    final boolean transferAfterCancelledWait(Node node) {
        if (compareAndSetWaitStatus(node, Node.CONDITION, 0)) {
            enq(node);
            return true;
        }
        /*
         * If we lost out to a signal(), then we can't proceed
         * until it finishes its enq().  Cancelling during an
         * incomplete transfer is both rare and transient, so just
         * spin.
         */
        while (!isOnSyncQueue(node))
            Thread.yield();
        return false;
    }


    final int fullyRelease(Node node) {
        boolean failed = true;
        try {
            int savedState = getState();
            if (release(savedState)) {
                failed = false;
                return savedState;
            } else {
                throw new IllegalMonitorStateException();
            }
        } finally {
            if (failed)
                node.waitStatus = Node.CANCELLED;
        }
    }

    // Instrumentation methods for conditions


    public final boolean owns(ConditionObject condition) {
        return condition.isOwnedBy(this);
    }


    public final boolean hasWaiters(ConditionObject condition) {
        if (!owns(condition))
            throw new IllegalArgumentException("Not owner");
        return condition.hasWaiters();
    }


    public final int getWaitQueueLength(ConditionObject condition) {
        if (!owns(condition))
            throw new IllegalArgumentException("Not owner");
        return condition.getWaitQueueLength();
    }


    public final Collection<Thread> getWaitingThreads(ConditionObject condition) {
        if (!owns(condition))
            throw new IllegalArgumentException("Not owner");
        return condition.getWaitingThreads();
    }


    public class ConditionObject implements Condition, java.io.Serializable {
        private static final long serialVersionUID = 1173984872572414699L;

        private transient Node firstWaiter;

        private transient Node lastWaiter;


        public ConditionObject() {
        }

        // Internal methods


        private Node addConditionWaiter() {
            Node t = lastWaiter;
            // If lastWaiter is cancelled, clean out.
            if (t != null && t.waitStatus != Node.CONDITION) {
                unlinkCancelledWaiters();
                t = lastWaiter;
            }
            Node node = new Node(Thread.currentThread(), Node.CONDITION);
            if (t == null)
                firstWaiter = node;
            else
                t.nextWaiter = node;
            lastWaiter = node;
            return node;
        }


        private void doSignal(Node first) {
            do {
                if ((firstWaiter = first.nextWaiter) == null)
                    lastWaiter = null;
                first.nextWaiter = null;
            } while (!transferForSignal(first) &&
                    (first = firstWaiter) != null);
        }


        private void doSignalAll(Node first) {
            lastWaiter = firstWaiter = null;
            do {
                Node next = first.nextWaiter;
                first.nextWaiter = null;
                transferForSignal(first);
                first = next;
            } while (first != null);
        }


        private void unlinkCancelledWaiters() {
            Node t = firstWaiter;
            Node trail = null;
            while (t != null) {
                Node next = t.nextWaiter;
                if (t.waitStatus != Node.CONDITION) {
                    t.nextWaiter = null;
                    if (trail == null)
                        firstWaiter = next;
                    else
                        trail.nextWaiter = next;
                    if (next == null)
                        lastWaiter = trail;
                } else
                    trail = t;
                t = next;
            }
        }

        // public methods


        public final void signal() {
            if (!isHeldExclusively())
                throw new IllegalMonitorStateException();
            Node first = firstWaiter;
            if (first != null)
                doSignal(first);
        }


        public final void signalAll() {
            if (!isHeldExclusively())
                throw new IllegalMonitorStateException();
            Node first = firstWaiter;
            if (first != null)
                doSignalAll(first);
        }


        public final void awaitUninterruptibly() {
            Node node = addConditionWaiter();
            int savedState = fullyRelease(node);
            boolean interrupted = false;
            while (!isOnSyncQueue(node)) {
                LockSupport.park(this);
                if (Thread.interrupted())
                    interrupted = true;
            }
            if (acquireQueued(node, savedState) || interrupted)
                selfInterrupt();
        }

        /*
         * For interruptible waits, we need to track whether to throw
         * InterruptedException, if interrupted while blocked on
         * condition, versus reinterrupt current thread, if
         * interrupted while blocked waiting to re-acquire.
         */


        private static final int REINTERRUPT = 1;

        private static final int THROW_IE = -1;


        private int checkInterruptWhileWaiting(Node node) {
            return Thread.interrupted() ?
                    (transferAfterCancelledWait(node) ? THROW_IE : REINTERRUPT) :
                    0;
        }


        private void reportInterruptAfterWait(int interruptMode)
                throws InterruptedException {
            if (interruptMode == THROW_IE)
                throw new InterruptedException();
            else if (interruptMode == REINTERRUPT)
                selfInterrupt();
        }

        /**
         * ww_m 条件队列 -- 加锁方法  只有获取到锁之后才能操作 所以实际上同步队列与条件队列没有任何关系 他们的关系是通过上下文产生的 没有相互指向的关系
         * @throws InterruptedException
         */
        public final void await() throws InterruptedException {
            if (Thread.interrupted())
                throw new InterruptedException();
            //1.加入到条件队列中去
            Node node = addConditionWaiter();
            int savedState = fullyRelease(node);
            int interruptMode = 0;
            while (!isOnSyncQueue(node)) {
                //阻塞
                LockSupport.park(this);
                if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
                    break;
            }
            if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
                interruptMode = REINTERRUPT;
            if (node.nextWaiter != null) // clean up if cancelled
                unlinkCancelledWaiters();
            if (interruptMode != 0)
                reportInterruptAfterWait(interruptMode);
        }


        public final long awaitNanos(long nanosTimeout)
                throws InterruptedException {
            if (Thread.interrupted())
                throw new InterruptedException();
            Node node = addConditionWaiter();
            int savedState = fullyRelease(node);
            final long deadline = System.nanoTime() + nanosTimeout;
            int interruptMode = 0;
            while (!isOnSyncQueue(node)) {
                if (nanosTimeout <= 0L) {
                    transferAfterCancelledWait(node);
                    break;
                }
                if (nanosTimeout >= spinForTimeoutThreshold)
                    LockSupport.parkNanos(this, nanosTimeout);
                if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
                    break;
                nanosTimeout = deadline - System.nanoTime();
            }
            if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
                interruptMode = REINTERRUPT;
            if (node.nextWaiter != null)
                unlinkCancelledWaiters();
            if (interruptMode != 0)
                reportInterruptAfterWait(interruptMode);
            return deadline - System.nanoTime();
        }


        public final boolean awaitUntil(Date deadline)
                throws InterruptedException {
            long abstime = deadline.getTime();
            if (Thread.interrupted())
                throw new InterruptedException();
            Node node = addConditionWaiter();
            int savedState = fullyRelease(node);
            boolean timedout = false;
            int interruptMode = 0;
            while (!isOnSyncQueue(node)) {
                if (System.currentTimeMillis() > abstime) {
                    timedout = transferAfterCancelledWait(node);
                    break;
                }
                LockSupport.parkUntil(this, abstime);
                if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
                    break;
            }
            if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
                interruptMode = REINTERRUPT;
            if (node.nextWaiter != null)
                unlinkCancelledWaiters();
            if (interruptMode != 0)
                reportInterruptAfterWait(interruptMode);
            return !timedout;
        }


        public final boolean await(long time, TimeUnit unit)
                throws InterruptedException {
            long nanosTimeout = unit.toNanos(time);
            if (Thread.interrupted())
                throw new InterruptedException();
            Node node = addConditionWaiter();
            int savedState = fullyRelease(node);
            final long deadline = System.nanoTime() + nanosTimeout;
            boolean timedout = false;
            int interruptMode = 0;
            while (!isOnSyncQueue(node)) {
                if (nanosTimeout <= 0L) {
                    timedout = transferAfterCancelledWait(node);
                    break;
                }
                if (nanosTimeout >= spinForTimeoutThreshold)
                    LockSupport.parkNanos(this, nanosTimeout);
                if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
                    break;
                nanosTimeout = deadline - System.nanoTime();
            }
            if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
                interruptMode = REINTERRUPT;
            if (node.nextWaiter != null)
                unlinkCancelledWaiters();
            if (interruptMode != 0)
                reportInterruptAfterWait(interruptMode);
            return !timedout;
        }

        //  support for instrumentation


        final boolean isOwnedBy(MyAbstractQueuedSynchronizer sync) {
            return sync == MyAbstractQueuedSynchronizer.this;
        }


        protected final boolean hasWaiters() {
            if (!isHeldExclusively())
                throw new IllegalMonitorStateException();
            for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
                if (w.waitStatus == Node.CONDITION)
                    return true;
            }
            return false;
        }


        protected final int getWaitQueueLength() {
            if (!isHeldExclusively())
                throw new IllegalMonitorStateException();
            int n = 0;
            for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
                if (w.waitStatus == Node.CONDITION)
                    ++n;
            }
            return n;
        }


        protected final Collection<Thread> getWaitingThreads() {
            if (!isHeldExclusively())
                throw new IllegalMonitorStateException();
            ArrayList<Thread> list = new ArrayList<Thread>();
            for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
                if (w.waitStatus == Node.CONDITION) {
                    Thread t = w.thread;
                    if (t != null)
                        list.add(t);
                }
            }
            return list;
        }
    }


    // getUnsafe 会判断 如果不是引导类加载器加载的类则不允许使用
    // private static final Unsafe unsafe = Unsafe.getUnsafe();
    private static final Unsafe unsafe;
    private static final long stateOffset;
    private static final long headOffset;
    private static final long tailOffset;
    private static final long waitStatusOffset;
    private static final long nextOffset;

    static {
        try {
            //通过反射创建 并获取
            //以线程安全的方式修改对应值
            Field getUnsafe = Unsafe.class.getDeclaredField("theUnsafe");
            getUnsafe.setAccessible(true);
            unsafe = (Unsafe) getUnsafe.get(null);
            stateOffset = unsafe.objectFieldOffset
                    (MyAbstractQueuedSynchronizer.class.getDeclaredField("state"));
            headOffset = unsafe.objectFieldOffset
                    (MyAbstractQueuedSynchronizer.class.getDeclaredField("head"));
            tailOffset = unsafe.objectFieldOffset
                    (MyAbstractQueuedSynchronizer.class.getDeclaredField("tail"));
            waitStatusOffset = unsafe.objectFieldOffset
                    (Node.class.getDeclaredField("waitStatus"));
            nextOffset = unsafe.objectFieldOffset
                    (Node.class.getDeclaredField("next"));

        } catch (Exception ex) {
            throw new Error(ex);
        }
    }


    /**
     * 更新头结点
     *
     * @param update
     * @return
     */
    private final boolean compareAndSetHead(Node update) {
        return unsafe.compareAndSwapObject(this, headOffset, null, update);
    }

    /**
     * 更新尾节点
     *
     * @param expect
     * @param update
     * @return
     */
    private final boolean compareAndSetTail(Node expect, Node update) {
        return unsafe.compareAndSwapObject(this, tailOffset, expect, update);
    }


    /**
     * 更新状态值
     *
     * @param node
     * @param expect
     * @param update
     * @return
     */
    private static final boolean compareAndSetWaitStatus(Node node,
                                                         int expect,
                                                         int update) {
        return unsafe.compareAndSwapInt(node, waitStatusOffset,
                expect, update);
    }

    /**
     * 更新后置节点
     *
     * @param node
     * @param expect
     * @param update
     * @return
     */
    private static final boolean compareAndSetNext(Node node,
                                                   Node expect,
                                                   Node update) {
        return unsafe.compareAndSwapObject(node, nextOffset, expect, update);
    }
}
